The present invention relates to a method for manipulating source data to determine a route from a predetermined starting point to a predetermined destination for a means of conveyance, in particular for a motor vehicle, airplane, or ship, based on a digital database that includes predetermined route segments ki with correspondingly assigned nodes ni that interconnect predetermined route segments ki, where respective weights gi are assigned to the route segments ki and/or the nodes ni.
Navigation systems, such as those based on GPS (Global Positioning System), help the driver of a means of conveyance to navigate a route to a predetermined destination. The navigation system selects an optimum path, i.e., route, at least on the basis of starting and destination coordinates and a corresponding digital database that is largely a representation of the real road grid. However, when a navigation system determines routes autonomously, existing navigation systems are partly or entirely unable to take into account real traffic events, such as traffic jams in a specific route segment.
The object of the present invention is to provide an improved method of the type mentioned in the preamble which eliminates the above-mentioned disadvantages and suitably converts the effects of such traffic events in a real traffic situation to a digital map.
According to the present invention, this is accomplished in that weights gi are varied, as a function of external events, before a route finding algorithm determines the route.
The advantage of this is that, particularly when determining an optimum route using a route finding algorithm, the alternative routes obtained after manipulating the existing digital map pay particularly close attention to the underlying, real traffic situation.
To achieve optimum routing, the route finding algorithm determines the route in a way that minimizes the sum of weights gi.
In one preferred embodiment of the method, weight gi is a length li of a route segment ki, a travel time tki of a route segment ki, and/or a waiting time tni at a node ni. A node can be, for example, a border crossing or a tollgate, and the waiting time refers to the respective processing time.
A data source suitably supplies data to vary weights gi that are processed in a data sink. The data source can be, for example, a traffic report receiver, an event data bank, and/or a data bank for mapping traffic reports to the database, and the data sink can be, for example, a traffic report data-processing software program in a navigation computer of the navigation system.
To vary the weights according to events, the external events are classified for predetermined weight variations by the data source and/or the data sink.
In one preferred embodiment, weight gi is a travel time tki of route segment ki, where a varied weight tkinew is obtained according to the following equation:             t              k        i            new        =                            l                      k            i                                    V          ⁡                      (                          k              i                        )                              ·              100                  Δ          ⁢                      xe2x80x83                    ⁢                      V            c                                ,
where V(ki) is an assumed velocity for route segment ki, and DVc is a variation in route segment velocity caused by an external event.
In an alternative, preferred embodiment, weight gi is a travel time tki of route segment ki, where the database has a hierarchical layout, and a varied weight tkinew is obtained according to the following equation:       t          k      i        new    =                    t                  k          i                          new          ⁡                      (            1            )                              -              t                  k          i                          new          ⁡                      (            2            )                                =                  (                                            l                              k                i                                                    V              ⁡                              (                                  k                  i                                )                                              ·                      100                          Δ              ⁢                              xe2x80x83                            ⁢                              V                c                                              ·                                    Δ              ⁢                              xe2x80x83                            ⁢                              l                levelj                                      100                          )            +              (                                            l                              k                i                                                    V              ⁡                              (                                  k                  i                                )                                              ·                      (                          1              -                                                Δ                  ⁢                                      xe2x80x83                                    ⁢                                      l                    levelj                                                  100                                      )                          )            
where V(ki) is an assumed velocity for route segment ki, DVc is a variation in route segment velocity caused by an external event, and D|Level j is the length percentage of overall edge length designating the proportionate manipulation on a generalization level j of the hierarchical database.